Système négabinaire
En mathématiques, le système négabinaire (base –2) est un système de numération positionnel non standard utilisé dans l'ordinateur expérimental polonais BINEG, construit en 1957-59. Il possède la propriété inhabituelle d'avoir les nombres négatifs et positifs représentés sans un bit de signe, bien que les opérations arithmétiques soient plus compliquées.
Histoire
[modifier | modifier le code]Les bases numériques négatives ont été découvertes par Vittorio Grünwald (en) dans son travail Giornale di Matematiche di Battaglini, publié en 1885. Grünwald donna des algorithmes pour exécuter les additions, les soustractions, les multiplications, les divisions, les extractions de racines, les tests de divisibilité et les conversions de bases. Les bases négatives furent redécouvertes indépendamment plus tard par Aubrey J. Kempner (en) en 1936 et Zdzisław Pawlak (en) et A. Wakulicz en 1959.
Écrire des nombres en négabinaire
[modifier | modifier le code]Tout entier relatif peut être écrit de manière unique sous la forme
où chaque chiffre dk est soit 0 ou 1 et le « bit conducteur » dn est 1 (à moins que n = 0). Le développement négabinaire d'un entier donné est alors donné par la chaîne :
Quelques nombres négabinaires ont la même représentation en système binaire. Par exemple,
est représenté par 10001 en binaire et 10001 en négabinaire.
Les nombres allant de –5 à 6 avec leurs développements négabinaires sont :
–5 1111 –4 1100 –3 1101 –2 10 –1 11 0 0 1 1 2 110 3 111 4 100 5 101 6 11010
Le développement négabinaire d'un nombre peut être trouvé avec une division répétée par –2, en enregistrant les restes non négatifs de 0 ou 1, en concaténant ces restes puis en démarrant avec le dernier. Note : si a / b = c, reste d, alors bc + d = a. Par exemple :
13 / –2 = –6, reste 1 –6 / –2 = 3, reste 0 3 / –2 = –1, reste 1 –1 / –2 = 1, reste 1 1 / –2 = 0, reste 1
Par conséquent, le développement négabinaire de 13 est 11101.
Note : les développements négabinaires d'entiers négatifs ont un nombre pair de bits, tandis que les développements négabinaires d'entiers positifs ont un nombre impair de bits.
Addition
[modifier | modifier le code]Pour ajouter deux nombres négabinaires, démarrer avec une retenue 0, et en démarrant à partir du bit de poids faible, ajouter les bits des deux nombres plus la retenue. Le nombre résultant est alors recherché dans la table suivante pour obtenir le bit à écrire dans le résultat, et la retenue suivante :
nombre bit retenue –2 0 1 (Note : –2 apparaît seulement pendant la soustraction). –1 1 1 0 0 0 1 1 0 2 0 –1 3 1 –1 (Note : 3 apparaît seulement pendant l'addition).
La deuxième ligne de cette table, par exemple, exprime le fait que –1 = 1 + 1×(–2); la cinquième ligne dit que 2 = 0 + –1×(–2); etc.
Comme exemple, ajouter 1010101 (1 + 4 + 16 + 64 = 85) et 1110100 (4 + 16 – 32 + 64 = 52),
retenue : 1 –1 0 –1 1 –1 0 0 0
premier nombre : 1 0 1 0 1 0 1
deuxième nombre : 1 1 1 0 1 0 0 +
--------------------------
nombre: 1 –1 2 0 3 –1 2 0 1
bit (résultat) : 1 1 0 0 1 1 0 0 1
retenue: 0 1 –1 0 –1 1 –1 0 0
donc, le résultat est 110011001 (1 – 8 + 16 – 128 + 256 = 137).
Soustraction
[modifier | modifier le code]Pour soustraire, multiplier chaque bit du deuxième nombre par –1, et ajouter les nombres, en utilisant la même table que ci-dessus.
Comme exemple, calculer 1101001 (1 – 8 – 32 + 64 = 25) moins 1110100 (4 + 16 – 32 + 64 = 52),
retenue : 0 1 –1 1 0 0 0
premier nombre : 1 1 0 1 0 0 1
deuxième nombre : –1 –1 –1 0 –1 0 0 +
--------------------
nombre: 0 1 –2 2 –1 0 1
bit (résultat) : 0 1 0 0 1 0 1
retenue: 0 0 1 –1 1 0 0
donc le résultat est 100101 (1 + 4 – 32 = –27).
Pour rendre négatif un nombre, calculer 0 moins le nombre.
Multiplication et division
[modifier | modifier le code]Décaler vers la gauche multiplie par –2, décaler vers la droite divise par –2.
Pour multiplier, multiplier comme en système décimal, mais en utilisant les règles négabinaires pour ajouter la retenue, lorsqu'on ajoute les nombres.
premier nombre : 1 1 1 0 1 1 0
deuxième nombre : 1 0 1 1 0 1 1 *
-------------------------------------
1 1 1 0 1 1 0
1 1 1 0 1 1 0
1 1 1 0 1 1 0
1 1 1 0 1 1 0
1 1 1 0 1 1 0 +
-------------------------------------
retenue: 0 –1 0 –1 –1 –1 –1 –1 0 –1 0 0
nombre: 1 0 2 1 2 2 2 3 2 0 2 1 0
bit (résultat) : 1 0 0 1 0 0 0 1 0 0 0 1 0
retenue : 0 –1 0 –1 –1 –1 –1 –1 0 –1 0 0
Pour chaque colonne, ajouter retenue à nombre, et diviser la somme par –2, pour obtenir la nouvelle retenue, et le bit résultant comme reste.
Références
[modifier | modifier le code]- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Negabinary » (voir la liste des auteurs).
- Vittorio Grünwald, Giornale di Matematiche di Battaglini (1885), 203-221, 367
- A. J. Kempner. (1936), 610-617
- Z. Pawlek et A. Wakulicz, Bulletin de l'Académie Polonaise des Sciences, Classe III, 5 (1957), 233-236; Série des sciences techniques 7 (1959), 713-721
- L. Wadel IRE Transactions EC-6 1957, 123
- N. M. Blachman, Communications of the ACM (1961), 257
- IEEE Transactions, 1963, 274-276
- Computer Design , 52-63
- R. W. Marczynski, Annotated History of Computing, 1980, 37-48
- Donald Knuth, The Art of Computer Programming, vol. 2, 3e éd., p. 204-205
Voir aussi
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- (en) Eric W. Weisstein, « Negabinary », sur MathWorld
